package bTree.LeetCode;

import java.util.ArrayList;
import java.util.List;

public class 生成不含相邻零的二进制字符串 {
    List<String> res = new ArrayList<>();

    public List<String> validStrings(int n) {
        StringBuilder sb=new StringBuilder();
        backTracking(sb,n);
        return res;
    }

    private void backTracking(StringBuilder sb, int n) {
        if (sb.length()==n){
            res.add(sb.toString());
            return;
        }
        for (int i=0;i<=1;i++){
            if (sb.isEmpty()){
                sb.append(i);
            }else {
                if (sb.charAt(sb.length()-1)=='0'&&i==0){
                    continue;
                }else {
                    sb.append(i);
                }
            }
            backTracking(sb,n);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}